package com.dyz.leetcode._09_heapAndPriorityQueue;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class _295_MedianFinder {
    //超时
//    private List<Integer> data;
//
//    public _295_MedianFinder() {
//        data = new ArrayList<>();
//
//    }
//
//    public void addNum(int num) {
//        data.add(num);
//    }
//
//    public double findMedian() {
//        Collections.sort(data);
//        int n = data.size();
//        if(n%2==1){
//            return data.get(n/2);
//        }else{
//            return (data.get(n/2)+data.get(n/2-1))/2.0;
//        }
//
//    }

    /**
     * 堆
     */
//    //大顶堆维护数据较小的一半元素
//    private PriorityQueue<Integer> maxHeap;
//
//    //小顶堆维护数据较大的一半元素
//    private PriorityQueue<Integer> minHeap;
//
//    //大顶堆和小顶堆
//    public _295_MedianFinder() {
//        maxHeap = new PriorityQueue<>((a, b)->b-a);
//        minHeap = new PriorityQueue<>((a, b)->a-b);
//    }
//
//    public void addNum(int num) {
//        if(maxHeap.isEmpty()){
//            maxHeap.add(num);
//            return;
//        }
//
//        if(num<=maxHeap.peek()){
//            maxHeap.add(num);
//        }else {
//            minHeap.add(num);
//        }
//
//        if(maxHeap.size()>minHeap.size()+1){
//            minHeap.add(maxHeap.remove());
//        }
//
//        if(minHeap.size()>maxHeap.size()){
//            maxHeap.add(minHeap.remove());
//        }
//    }
//
//    public double findMedian() {
//        if(maxHeap.size()>minHeap.size()){
//            return maxHeap.peek();
//        }else {
//            return (maxHeap.peek()+minHeap.peek())*0.5;
//        }
//    }

}
